package leetcode_201_300;

import java.util.HashSet;
import java.util.Set;

public class LeeCode_204 {
    public static void main(String[] args) {
        System.out.println(countPrimes(10));
    }

    private static int countPrimes(int n) {
        boolean[] dp = new boolean[n];
        if (n <= 2)
            return 0;
        int ans = 1;
        for (int i = 2; i < n; i += 2) {
            dp[i] = true;
        }
        for (int i = 3; i < n; i += 2) {
            if (dp[i])
                continue;
            ans++;
            for (int j = i; j < n; j += i) {
                dp[j] = true;
            }
        }
        return ans;
    }
}
